skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


  • Home
  • Search Results
  • Page 1 of 1

Search for: All records

Creators/Authors contains: "Adrian Dumitrescu"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. ; (, Proc. 34th International Workshop on Combinatorial Algorithms)
    For a polygon P with holes in the plane, we denote by ρ(P ) the ratio between the geodesic and the Euclidean diameters of P . It is shown that over all convex polygons with h convex holes, the supremum of ρ(P ) is between Ω(h1/3) and O(h1/2). The upper bound improves to O(1 + min{h3/4∆, h1/2∆1/2}) if every hole has diameter at most ∆ ·diam2(P ); and to O(1) if every hole is a fat convex polygon. Furthermore, we show that the function g(h) = supP ρ(P ) over convex polygons with h convex holes has the same growth rate as an analogous quantity over geometric triangulations with h vertices when h → ∞ 
    more » « less
    Accepted Manuscript Full Text Available
  2. ; (, Combinatorial Algorithms (IWOCA 2023))
    For a polygon P with holes in the plane, we denote by ϱ(P) the ratio between the geodesic and the Euclidean diameters of P. It is shown that over all convex polygons with h convex holes, the supremum of ϱ(P) is between Ω(h1/3) and O(h1/2) . The upper bound improves to O(1+min{h3/4Δ,h1/2Δ1/2}) if every hole has diameter at most Δ⋅diam2(P) ; and to O(1) if every hole is a fat convex polygon. Furthermore, we show that the function g(h)=supPϱ(P) over convex polygons with h convex holes has the same growth rate as an analogous quantity over geometric triangulations with h vertices when h→∞ . 
    more » « less
    Full Text Available